﻿/*
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at 
 * 
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
using System;
using java = biz.ritter.javapi;

namespace org.apache.harmony.awt.gl
{
    /**
     * @author Denis M. Kishenko
     */

    internal class Crossing
    {

        /**
         * Allowable tolerance for bounds comparison
         */
        const double DELTA = 1E-5;

        /**
         * If roots have distance less then <code>ROOT_DELTA</code> they are double
         */
        const double ROOT_DELTA = 1E-10;

        /**
         * Rectangle cross segment
         */
        public const int CROSSING = 255;

        /**
         * Unknown crossing result
         */
        const int UNKNOWN = 254;

        /**
         * Solves quadratic equation
         * @param eqn - the coefficients of the equation
         * @param res - the roots of the equation
         * @return a number of roots
         */
        public static int solveQuad(double[] eqn, double[] res)
        {
            double a = eqn[2];
            double b = eqn[1];
            double c = eqn[0];
            int rc = 0;
            if (a == 0.0)
            {
                if (b == 0.0)
                {
                    return -1;
                }
                res[rc++] = -c / b;
            }
            else
            {
                double d = b * b - 4.0 * a * c;
                // d < 0.0
                if (d < 0.0)
                {
                    return 0;
                }
                d = java.lang.Math.sqrt(d);
                res[rc++] = (-b + d) / (a * 2.0);
                // d != 0.0
                if (d != 0.0)
                {
                    res[rc++] = (-b - d) / (a * 2.0);
                }
            }
            return fixRoots(res, rc);
        }

        /**
         * Solves cubic equation
         * @param eqn - the coefficients of the equation
         * @param res - the roots of the equation
         * @return a number of roots
         */
        public static int solveCubic(double[] eqn, double[] res)
        {
            double d = eqn[3];
            if (d == 0)
            {
                return solveQuad(eqn, res);
            }
            double a = eqn[2] / d;
            double b = eqn[1] / d;
            double c = eqn[0] / d;
            int rc = 0;

            double Q = (a * a - 3.0 * b) / 9.0;
            double R = (2.0 * a * a * a - 9.0 * a * b + 27.0 * c) / 54.0;
            double Q3 = Q * Q * Q;
            double R2 = R * R;
            double n = -a / 3.0;

            if (R2 < Q3)
            {
                double t = java.lang.Math.acos(R / java.lang.Math.sqrt(Q3)) / 3.0;
                double p = 2.0 * java.lang.Math.PI / 3.0;
                double m = -2.0 * java.lang.Math.sqrt(Q);
                res[rc++] = m * java.lang.Math.cos(t) + n;
                res[rc++] = m * java.lang.Math.cos(t + p) + n;
                res[rc++] = m * java.lang.Math.cos(t - p) + n;
            }
            else
            {
                //          Debug.println("R2 >= Q3 (" + R2 + "/" + Q3 + ")");
                double A = java.lang.Math.pow(java.lang.Math.abs(R) + java.lang.Math.sqrt(R2 - Q3), 1.0 / 3.0);
                if (R > 0.0)
                {
                    A = -A;
                }
                //          if (A == 0.0) {
                if (-ROOT_DELTA < A && A < ROOT_DELTA)
                {
                    res[rc++] = n;
                }
                else
                {
                    double B = Q / A;
                    res[rc++] = A + B + n;
                    //              if (R2 == Q3) {
                    double delta = R2 - Q3;
                    if (-ROOT_DELTA < delta && delta < ROOT_DELTA)
                    {
                        res[rc++] = -(A + B) / 2.0 + n;
                    }
                }

            }
            return fixRoots(res, rc);
        }

        /**
         * Excludes double roots. Roots are double if they lies enough close with each other. 
         * @param res - the roots 
         * @param rc - the roots count
         * @return new roots count
         */
        static int fixRoots(double[] res, int rc)
        {
            int tc = 0;
            for (int i = 0; i < rc; i++)
            {
                {
                    bool outer = false;
                    for (int j = i + 1; j < rc; j++)
                    {
                        if (isZero(res[i] - res[j]))
                        {
                            outer = true;
                            j = rc;
                        }
                    }
                    if (!outer)
                    {
                        res[tc++] = res[i];
                    }
                }
            }
            return tc;
        }

        /**
         * QuadCurve class provides basic functionality to find curve crossing and calculating bounds
         */
        public class QuadCurve
        {

            internal double ax, ay, bx, by;
            double Ax, Ay, Bx, By;

            public QuadCurve(double x1, double y1, double cx, double cy, double x2, double y2)
            {
                ax = x2 - x1;
                ay = y2 - y1;
                bx = cx - x1;
                by = cy - y1;

                Bx = bx + bx;   // Bx = 2.0 * bx
                Ax = ax - Bx;   // Ax = ax - 2.0 * bx

                By = by + by;   // By = 2.0 * by
                Ay = ay - By;   // Ay = ay - 2.0 * by
            }

            internal int cross(double[] res, int rc, double py1, double py2)
            {
                int cross = 0;

                for (int i = 0; i < rc; i++)
                {
                    double t = res[i];

                    // CURVE-OUTSIDE
                    if (t < -DELTA || t > 1 + DELTA)
                    {
                        continue;
                    }
                    // CURVE-START
                    if (t < DELTA)
                    {
                        if (py1 < 0.0 && (bx != 0.0 ? bx : ax - bx) < 0.0)
                        {
                            cross--;
                        }
                        continue;
                    }
                    // CURVE-END
                    if (t > 1 - DELTA)
                    {
                        if (py1 < ay && (ax != bx ? ax - bx : bx) > 0.0)
                        {
                            cross++;
                        }
                        continue;
                    }
                    // CURVE-INSIDE
                    double ry = t * (t * Ay + By);
                    // ry = t * t * Ay + t * By
                    if (ry > py2)
                    {
                        double rxt = t * Ax + bx;
                        // rxt = 2.0 * t * Ax + Bx = 2.0 * t * Ax + 2.0 * bx
                        if (rxt > -DELTA && rxt < DELTA)
                        {
                            continue;
                        }
                        cross += rxt > 0.0 ? 1 : -1;
                    }
                } // for

                return cross;
            }

            internal int solvePoint(double[] res, double px)
            {
                double[] eqn = { -px, Bx, Ax };
                return solveQuad(eqn, res);
            }

            internal int solveExtrem(double[] res)
            {
                int rc = 0;
                if (Ax != 0.0)
                {
                    res[rc++] = -Bx / (Ax + Ax);
                }
                if (Ay != 0.0)
                {
                    res[rc++] = -By / (Ay + Ay);
                }
                return rc;
            }

            internal int addBound(double[] bound, int bc, double[] res, int rc, double minX, double maxX, bool changeId, int id)
            {
                for (int i = 0; i < rc; i++)
                {
                    double t = res[i];
                    if (t > -DELTA && t < 1 + DELTA)
                    {
                        double rx = t * (t * Ax + Bx);
                        if (minX <= rx && rx <= maxX)
                        {
                            bound[bc++] = t;
                            bound[bc++] = rx;
                            bound[bc++] = t * (t * Ay + By);
                            bound[bc++] = id;
                            if (changeId)
                            {
                                id++;
                            }
                        }
                    }
                }
                return bc;
            }

        }

        /**
         * CubicCurve class provides basic functionality to find curve crossing and calculating bounds
         */
        public class CubicCurve
        {

            internal double ax, ay, bx, by, cx, cy;
            double Ax, Ay, Bx, By, Cx, Cy;
            double Ax3, Bx2;

            public CubicCurve(double x1, double y1, double cx1, double cy1, double cx2, double cy2, double x2, double y2)
            {
                ax = x2 - x1;
                ay = y2 - y1;
                bx = cx1 - x1;
                by = cy1 - y1;
                cx = cx2 - x1;
                cy = cy2 - y1;

                Cx = bx + bx + bx;           // Cx = 3.0 * bx
                Bx = cx + cx + cx - Cx - Cx; // Bx = 3.0 * cx - 6.0 * bx
                Ax = ax - Bx - Cx;           // Ax = ax - 3.0 * cx + 3.0 * bx

                Cy = by + by + by;           // Cy = 3.0 * by
                By = cy + cy + cy - Cy - Cy; // By = 3.0 * cy - 6.0 * by
                Ay = ay - By - Cy;           // Ay = ay - 3.0 * cy + 3.0 * by

                Ax3 = Ax + Ax + Ax;
                Bx2 = Bx + Bx;
            }

            internal int cross(double[] res, int rc, double py1, double py2)
            {
                int cross = 0;
                for (int i = 0; i < rc; i++)
                {
                    double t = res[i];

                    // CURVE-OUTSIDE
                    if (t < -DELTA || t > 1 + DELTA)
                    {
                        continue;
                    }
                    // CURVE-START
                    if (t < DELTA)
                    {
                        if (py1 < 0.0 && (bx != 0.0 ? bx : (cx != bx ? cx - bx : ax - cx)) < 0.0)
                        {
                            cross--;
                        }
                        continue;
                    }
                    // CURVE-END
                    if (t > 1 - DELTA)
                    {
                        if (py1 < ay && (ax != cx ? ax - cx : (cx != bx ? cx - bx : bx)) > 0.0)
                        {
                            cross++;
                        }
                        continue;
                    }
                    // CURVE-INSIDE
                    double ry = t * (t * (t * Ay + By) + Cy);
                    // ry = t * t * t * Ay + t * t * By + t * Cy
                    if (ry > py2)
                    {
                        double rxt = t * (t * Ax3 + Bx2) + Cx;
                        // rxt = 3.0 * t * t * Ax + 2.0 * t * Bx + Cx
                        if (rxt > -DELTA && rxt < DELTA)
                        {
                            rxt = t * (Ax3 + Ax3) + Bx2;
                            // rxt = 6.0 * t * Ax + 2.0 * Bx
                            if (rxt < -DELTA || rxt > DELTA)
                            {
                                // Inflection point
                                continue;
                            }
                            rxt = ax;
                        }
                        cross += rxt > 0.0 ? 1 : -1;
                    }
                } //for

                return cross;
            }

            internal int solvePoint(double[] res, double px)
            {
                double[] eqn = { -px, Cx, Bx, Ax };
                return solveCubic(eqn, res);
            }

            internal int solveExtremX(double[] res)
            {
                double[] eqn = { Cx, Bx2, Ax3 };
                return solveQuad(eqn, res);
            }

            internal int solveExtremY(double[] res)
            {
                double[] eqn = { Cy, By + By, Ay + Ay + Ay };
                return solveQuad(eqn, res);
            }

            internal int addBound(double[] bound, int bc, double[] res, int rc, double minX, double maxX, bool changeId, int id)
            {
                for (int i = 0; i < rc; i++)
                {
                    double t = res[i];
                    if (t > -DELTA && t < 1 + DELTA)
                    {
                        double rx = t * (t * (t * Ax + Bx) + Cx);
                        if (minX <= rx && rx <= maxX)
                        {
                            bound[bc++] = t;
                            bound[bc++] = rx;
                            bound[bc++] = t * (t * (t * Ay + By) + Cy);
                            bound[bc++] = id;
                            if (changeId)
                            {
                                id++;
                            }
                        }
                    }
                }
                return bc;
            }

        }

        /**
         * Returns how many times ray from point (x,y) cross line.
         */
        public static int crossLine(double x1, double y1, double x2, double y2, double x, double y)
        {

            // LEFT/RIGHT/UP/EMPTY
            if ((x < x1 && x < x2) ||
                (x > x1 && x > x2) ||
                (y > y1 && y > y2) ||
                (x1 == x2))
            {
                return 0;
            }

            // DOWN
            if (y < y1 && y < y2)
            {
            }
            else
            {
                // INSIDE
                if ((y2 - y1) * (x - x1) / (x2 - x1) <= y - y1)
                {
                    // INSIDE-UP
                    return 0;
                }
            }

            // START
            if (x == x1)
            {
                return x1 < x2 ? 0 : -1;
            }

            // END
            if (x == x2)
            {
                return x1 < x2 ? 1 : 0;
            }

            // INSIDE-DOWN
            return x1 < x2 ? 1 : -1;
        }

        /**
         * Returns how many times ray from point (x,y) cross quard curve
         */
        public static int crossQuad(double x1, double y1, double cx, double cy, double x2, double y2, double x, double y)
        {

            // LEFT/RIGHT/UP/EMPTY
            if ((x < x1 && x < cx && x < x2) ||
                (x > x1 && x > cx && x > x2) ||
                (y > y1 && y > cy && y > y2) ||
                (x1 == cx && cx == x2))
            {
                return 0;
            }

            // DOWN
            if (y < y1 && y < cy && y < y2 && x != x1 && x != x2)
            {
                if (x1 < x2)
                {
                    return x1 < x && x < x2 ? 1 : 0;
                }
                return x2 < x && x < x1 ? -1 : 0;
            }

            // INSIDE
            QuadCurve c = new QuadCurve(x1, y1, cx, cy, x2, y2);
            double px = x - x1;
            double py = y - y1;
            double[] res = new double[3];
            int rc = c.solvePoint(res, px);

            return c.cross(res, rc, py, py);
        }

        /**
         * Returns how many times ray from point (x,y) cross cubic curve
         */
        public static int crossCubic(double x1, double y1, double cx1, double cy1, double cx2, double cy2, double x2, double y2, double x, double y)
        {

            // LEFT/RIGHT/UP/EMPTY
            if ((x < x1 && x < cx1 && x < cx2 && x < x2) ||
                (x > x1 && x > cx1 && x > cx2 && x > x2) ||
                (y > y1 && y > cy1 && y > cy2 && y > y2) ||
                (x1 == cx1 && cx1 == cx2 && cx2 == x2))
            {
                return 0;
            }

            // DOWN
            if (y < y1 && y < cy1 && y < cy2 && y < y2 && x != x1 && x != x2)
            {
                if (x1 < x2)
                {
                    return x1 < x && x < x2 ? 1 : 0;
                }
                return x2 < x && x < x1 ? -1 : 0;
            }

            // INSIDE
            CubicCurve c = new CubicCurve(x1, y1, cx1, cy1, cx2, cy2, x2, y2);
            double px = x - x1;
            double py = y - y1;
            double[] res = new double[3];
            int rc = c.solvePoint(res, px);
            return c.cross(res, rc, py, py);
        }

        /**
         * Returns how many times ray from point (x,y) cross path
         */
        public static int crossPath(java.awt.geom.PathIterator p, double x, double y)
        {
            int cross = 0;
            double mx, my, cx, cy;
            mx = my = cx = cy = 0.0;
            double[] coords = new double[6];

            while (!p.isDone())
            {
                switch (p.currentSegment(coords))
                {
                    case java.awt.geom.PathIteratorConstants.SEG_MOVETO:
                        if (cx != mx || cy != my)
                        {
                            cross += crossLine(cx, cy, mx, my, x, y);
                        }
                        mx = cx = coords[0];
                        my = cy = coords[1];
                        break;
                    case java.awt.geom.PathIteratorConstants.SEG_LINETO:
                        cross += crossLine(cx, cy, cx = coords[0], cy = coords[1], x, y);
                        break;
                    case java.awt.geom.PathIteratorConstants.SEG_QUADTO:
                        cross += crossQuad(cx, cy, coords[0], coords[1], cx = coords[2], cy = coords[3], x, y);
                        break;
                    case java.awt.geom.PathIteratorConstants.SEG_CUBICTO:
                        cross += crossCubic(cx, cy, coords[0], coords[1], coords[2], coords[3], cx = coords[4], cy = coords[5], x, y);
                        break;
                    case java.awt.geom.PathIteratorConstants.SEG_CLOSE:
                        if (cy != my || cx != mx)
                        {
                            cross += crossLine(cx, cy, cx = mx, cy = my, x, y);
                        }
                        break;
                }

                // checks if the point (x,y) is the vertex of shape with PathIterator p           
                if (x == cx && y == cy)
                {
                    cross = 0;
                    cy = my;
                    break;
                }
                p.next();
            }
            if (cy != my)
            {
                cross += crossLine(cx, cy, mx, my, x, y);
            }
            return cross;
        }

        /**
         * Returns how many times ray from point (x,y) cross shape
         */
        public static int crossShape(java.awt.Shape s, double x, double y)
        {
            if (!s.getBounds2D().contains(x, y))
            {
                return 0;
            }
            return crossPath(s.getPathIterator(null), x, y);
        }

        /**
         * Returns true if value enough small
         */
        public static bool isZero(double val)
        {
            return -DELTA < val && val < DELTA;
        }

        /**
         * Sort bound array
         */
        static void sortBound(double[] bound, int bc)
        {
            for (int i = 0; i < bc - 4; i += 4)
            {
                int k = i;
                for (int j = i + 4; j < bc; j += 4)
                {
                    if (bound[k] > bound[j])
                    {
                        k = j;
                    }
                }
                if (k != i)
                {
                    double tmp = bound[i];
                    bound[i] = bound[k];
                    bound[k] = tmp;
                    tmp = bound[i + 1];
                    bound[i + 1] = bound[k + 1];
                    bound[k + 1] = tmp;
                    tmp = bound[i + 2];
                    bound[i + 2] = bound[k + 2];
                    bound[k + 2] = tmp;
                    tmp = bound[i + 3];
                    bound[i + 3] = bound[k + 3];
                    bound[k + 3] = tmp;
                }
            }
        }

        /**
         * Returns are bounds intersect or not intersect rectangle 
         */
        static int crossBound(double[] bound, int bc, double py1, double py2)
        {

            // LEFT/RIGHT
            if (bc == 0)
            {
                return 0;
            }

            // Check Y coordinate
            int up = 0;
            int down = 0;
            for (int i = 2; i < bc; i += 4)
            {
                if (bound[i] < py1)
                {
                    up++;
                    continue;
                }
                if (bound[i] > py2)
                {
                    down++;
                    continue;
                }
                return CROSSING;
            }

            // UP
            if (down == 0)
            {
                return 0;
            }

            if (up != 0)
            {
                // bc >= 2
                sortBound(bound, bc);
                bool sign = bound[2] > py2;
                for (int i = 6; i < bc; i += 4)
                {
                    bool sign2 = bound[i] > py2;
                    if (sign != sign2 && bound[i + 1] != bound[i - 3])
                    {
                        return CROSSING;
                    }
                    sign = sign2;
                }
            }
            return UNKNOWN;
        }

        /**
         * Returns how many times rectangle stripe cross line or the are intersect
         */
        public static int intersectLine(double x1, double y1, double x2, double y2, double rx1, double ry1, double rx2, double ry2)
        {

            // LEFT/RIGHT/UP
            if ((rx2 < x1 && rx2 < x2) ||
                (rx1 > x1 && rx1 > x2) ||
                (ry1 > y1 && ry1 > y2))
            {
                return 0;
            }

            // DOWN
            if (ry2 < y1 && ry2 < y2)
            {
            }
            else
            {

                // INSIDE
                if (x1 == x2)
                {
                    return CROSSING;
                }

                // Build bound
                double bx1, bx2;
                if (x1 < x2)
                {
                    bx1 = x1 < rx1 ? rx1 : x1;
                    bx2 = x2 < rx2 ? x2 : rx2;
                }
                else
                {
                    bx1 = x2 < rx1 ? rx1 : x2;
                    bx2 = x1 < rx2 ? x1 : rx2;
                }
                double k = (y2 - y1) / (x2 - x1);
                double by1 = k * (bx1 - x1) + y1;
                double by2 = k * (bx2 - x1) + y1;

                // BOUND-UP
                if (by1 < ry1 && by2 < ry1)
                {
                    return 0;
                }

                // BOUND-DOWN
                if (by1 > ry2 && by2 > ry2)
                {
                }
                else
                {
                    return CROSSING;
                }
            }

            // EMPTY
            if (x1 == x2)
            {
                return 0;
            }

            // CURVE-START
            if (rx1 == x1)
            {
                return x1 < x2 ? 0 : -1;
            }

            // CURVE-END
            if (rx1 == x2)
            {
                return x1 < x2 ? 1 : 0;
            }

            if (x1 < x2)
            {
                return x1 < rx1 && rx1 < x2 ? 1 : 0;
            }
            return x2 < rx1 && rx1 < x1 ? -1 : 0;

        }

        /**
         * Returns how many times rectangle stripe cross quad curve or the are intersect
         */
        public static int intersectQuad(double x1, double y1, double cx, double cy, double x2, double y2, double rx1, double ry1, double rx2, double ry2)
        {

            // LEFT/RIGHT/UP ------------------------------------------------------
            if ((rx2 < x1 && rx2 < cx && rx2 < x2) ||
                (rx1 > x1 && rx1 > cx && rx1 > x2) ||
                (ry1 > y1 && ry1 > cy && ry1 > y2))
            {
                return 0;
            }

            // DOWN ---------------------------------------------------------------
            if (ry2 < y1 && ry2 < cy && ry2 < y2 && rx1 != x1 && rx1 != x2)
            {
                if (x1 < x2)
                {
                    return x1 < rx1 && rx1 < x2 ? 1 : 0;
                }
                return x2 < rx1 && rx1 < x1 ? -1 : 0;
            }

            // INSIDE -------------------------------------------------------------
            QuadCurve c = new QuadCurve(x1, y1, cx, cy, x2, y2);
            double px1 = rx1 - x1;
            double py1 = ry1 - y1;
            double px2 = rx2 - x1;
            double py2 = ry2 - y1;

            double[] res1 = new double[3];
            double[] res2 = new double[3];
            int rc1 = c.solvePoint(res1, px1);
            int rc2 = c.solvePoint(res2, px2);

            // INSIDE-LEFT/RIGHT
            if (rc1 == 0 && rc2 == 0)
            {
                return 0;
            }

            // Build bound --------------------------------------------------------
            double minX = px1 - DELTA;
            double maxX = px2 + DELTA;
            double[] bound = new double[28];
            int bc = 0;
            // Add roots
            bc = c.addBound(bound, bc, res1, rc1, minX, maxX, false, 0);
            bc = c.addBound(bound, bc, res2, rc2, minX, maxX, false, 1);
            // Add extremal points`
            rc2 = c.solveExtrem(res2);
            bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 2);
            // Add start and end
            if (rx1 < x1 && x1 < rx2)
            {
                bound[bc++] = 0.0;
                bound[bc++] = 0.0;
                bound[bc++] = 0.0;
                bound[bc++] = 4;
            }
            if (rx1 < x2 && x2 < rx2)
            {
                bound[bc++] = 1.0;
                bound[bc++] = c.ax;
                bound[bc++] = c.ay;
                bound[bc++] = 5;
            }
            // End build bound ----------------------------------------------------

            int cross = crossBound(bound, bc, py1, py2);
            if (cross != UNKNOWN)
            {
                return cross;
            }
            return c.cross(res1, rc1, py1, py2);
        }

        /**
         * Returns how many times rectangle stripe cross cubic curve or the are intersect
         */
        public static int intersectCubic(double x1, double y1, double cx1, double cy1, double cx2, double cy2, double x2, double y2, double rx1, double ry1, double rx2, double ry2)
        {

            // LEFT/RIGHT/UP
            if ((rx2 < x1 && rx2 < cx1 && rx2 < cx2 && rx2 < x2) ||
                (rx1 > x1 && rx1 > cx1 && rx1 > cx2 && rx1 > x2) ||
                (ry1 > y1 && ry1 > cy1 && ry1 > cy2 && ry1 > y2))
            {
                return 0;
            }

            // DOWN
            if (ry2 < y1 && ry2 < cy1 && ry2 < cy2 && ry2 < y2 && rx1 != x1 && rx1 != x2)
            {
                if (x1 < x2)
                {
                    return x1 < rx1 && rx1 < x2 ? 1 : 0;
                }
                return x2 < rx1 && rx1 < x1 ? -1 : 0;
            }

            // INSIDE
            CubicCurve c = new CubicCurve(x1, y1, cx1, cy1, cx2, cy2, x2, y2);
            double px1 = rx1 - x1;
            double py1 = ry1 - y1;
            double px2 = rx2 - x1;
            double py2 = ry2 - y1;

            double[] res1 = new double[3];
            double[] res2 = new double[3];
            int rc1 = c.solvePoint(res1, px1);
            int rc2 = c.solvePoint(res2, px2);

            // LEFT/RIGHT
            if (rc1 == 0 && rc2 == 0)
            {
                return 0;
            }

            double minX = px1 - DELTA;
            double maxX = px2 + DELTA;

            // Build bound --------------------------------------------------------
            double[] bound = new double[40];
            int bc = 0;
            // Add roots
            bc = c.addBound(bound, bc, res1, rc1, minX, maxX, false, 0);
            bc = c.addBound(bound, bc, res2, rc2, minX, maxX, false, 1);
            // Add extrimal points
            rc2 = c.solveExtremX(res2);
            bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 2);
            rc2 = c.solveExtremY(res2);
            bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 4);
            // Add start and end
            if (rx1 < x1 && x1 < rx2)
            {
                bound[bc++] = 0.0;
                bound[bc++] = 0.0;
                bound[bc++] = 0.0;
                bound[bc++] = 6;
            }
            if (rx1 < x2 && x2 < rx2)
            {
                bound[bc++] = 1.0;
                bound[bc++] = c.ax;
                bound[bc++] = c.ay;
                bound[bc++] = 7;
            }
            // End build bound ----------------------------------------------------

            int cross = crossBound(bound, bc, py1, py2);
            if (cross != UNKNOWN)
            {
                return cross;
            }
            return c.cross(res1, rc1, py1, py2);
        }

        /**
         * Returns how many times rectangle stripe cross path or the are intersect
         */
        public static int intersectPath(java.awt.geom.PathIterator p, double x, double y, double w, double h)
        {

            int cross = 0;
            int count;
            double mx, my, cx, cy;
            mx = my = cx = cy = 0.0;
            double[] coords = new double[6];

            double rx1 = x;
            double ry1 = y;
            double rx2 = x + w;
            double ry2 = y + h;

            while (!p.isDone())
            {
                count = 0;
                switch (p.currentSegment(coords))
                {
                    case java.awt.geom.PathIteratorConstants.SEG_MOVETO:
                        if (cx != mx || cy != my)
                        {
                            count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2);
                        }
                        mx = cx = coords[0];
                        my = cy = coords[1];
                        break;
                    case java.awt.geom.PathIteratorConstants.SEG_LINETO:
                        count = intersectLine(cx, cy, cx = coords[0], cy = coords[1], rx1, ry1, rx2, ry2);
                        break;
                    case java.awt.geom.PathIteratorConstants.SEG_QUADTO:
                        count = intersectQuad(cx, cy, coords[0], coords[1], cx = coords[2], cy = coords[3], rx1, ry1, rx2, ry2);
                        break;
                    case java.awt.geom.PathIteratorConstants.SEG_CUBICTO:
                        count = intersectCubic(cx, cy, coords[0], coords[1], coords[2], coords[3], cx = coords[4], cy = coords[5], rx1, ry1, rx2, ry2);
                        break;
                    case java.awt.geom.PathIteratorConstants.SEG_CLOSE:
                        if (cy != my || cx != mx)
                        {
                            count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2);
                        }
                        cx = mx;
                        cy = my;
                        break;
                }
                if (count == CROSSING)
                {
                    return CROSSING;
                }
                cross += count;
                p.next();
            }
            if (cy != my)
            {
                count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2);
                if (count == CROSSING)
                {
                    return CROSSING;
                }
                cross += count;
            }
            return cross;
        }

        /**
         * Returns how many times rectangle stripe cross shape or the are intersect
         */
        public static int intersectShape(java.awt.Shape s, double x, double y, double w, double h)
        {
            if (!s.getBounds2D().intersects(x, y, w, h))
            {
                return 0;
            }
            return intersectPath(s.getPathIterator(null), x, y, w, h);
        }

        /**
         * Returns true if cross count correspond inside location for non zero path rule
         */
        public static bool isInsideNonZero(int cross)
        {
            return cross != 0;
        }

        /**
         * Returns true if cross count correspond inside location for even-odd path rule
         */
        public static bool isInsideEvenOdd(int cross)
        {
            return (cross & 1) != 0;
        }
    }
}
